package main

import (
	"fmt"
	"sort"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.4 MB, 在所有 Go 提交中击败了80.58%的用户
 */
var ans [][]int
var path []int

func subsetsWithDup(nums []int) [][]int {

	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})

	ans = [][]int{}
	path = []int{}
	dfs(nums, 0)
	return ans
}

func dfs(nums []int, u int) {

	if u == len(nums) {
		t := make([]int, len(path))
		copy(t, path)
		ans = append(ans, t)
		return
	}

	k := u + 1
	for k < len(nums) && nums[k] == nums[u] { k++ }

	for i := 0; i <= k - u; i++ {
		dfs(nums, k)
		path = append(path, nums[u])
	}

	for i := 0; i <= k - u; i++ {
		path = path[:len(path) - 1]
	}
}

func main() {

	nums := []int{1, 1, 2}
	fmt.Println(subsetsWithDup(nums))
}
